package com.kevin.Code.DP;

/**
 * @author Vinlee Xiao
 * @Classname DistinctSubsequences
 * @Description Leetcode 115. 不同的子序列  难度 困难 没啥思路
 * @Date 2021/10/5 15:05
 * @Version 1.0
 */
public class DistinctSubsequences {


    /**
     * 找状态转移方程依然是题目的关键
     *
     * @param s
     * @param t
     * @return
     */
    public int numDistinct(String s, String t) {

        int m = s.length();
        int n = t.length();


        if (m < n) {
            return 0;
        }

        //设置状态转移数组 1.明确状态转移数组的含义
        //dp[i][j]表示i...字符串中包含 j...的个数 [i][n...n]=0
        int[][] dp = new int[m + 1][n + 1];

        //dp数组的边界处理 当t的长度为空时
        for (int i = 0; i < m + 1; i++) {
            dp[i][n] = 1;
        }

        for (int i = m - 1; i >= 0; i--) {

            for (int j = n - 1; j >= 0; j--) {

                //当字符
                if (s.charAt(i) == t.charAt(j)) {
                    //两种选择 两个字符匹配 坐标移动向上 也可以选择不匹配 i坐标向上移动
                    dp[i][j] = dp[i + 1][j + 1] + dp[i + 1][j];
                } else {
                    dp[i][j] = dp[i + 1][j];
                }
            }
        }


        return dp[0][0];
    }


    /**
     * @param s
     * @param t
     * @return
     */
    public int numDistinct1(String s, String t) {

        int m = s.length();
        int n = t.length();


        if (m < n) {
            return 0;
        }


        int[][] dp = new int[m + 1][n + 1];

        //设置状态转移数组 1.明确状态转移数组的含义
        //dp[i][j]表示i...字符串中包含 j...的个数 [i][0...0]=0
        //dp数组的边界处理 当t的长度为空时
        for (int i = 0; i < m + 1; i++) {
            dp[i][0] = 1;
        }

        for (int i = 1; i < m + 1; i++) {
            char s1 = s.charAt(i - 1);
            for (int j = 1; j < n + 1; j++) {

                if (s1 == t.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }

            }
        }

        return dp[m][n];
    }


    public static void main(String[] args) {
        DistinctSubsequences distinctSubsequences = new DistinctSubsequences();
        int i = distinctSubsequences.numDistinct1("rabbbit", "rabbit");
        System.out.println(i);
    }

}
